package com.moon.leetcode;

// 309. 最佳买卖股票时机含冷冻期
//
//给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
//
//
// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
//
// 示例:
//
// 输入: [1,2,3,0,2]
//输出: 3
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
// Related Topics 动态规划
// 👍 739 👎 0
public class No309_maxProfit {

    public static void main(String[] args) {
        System.out.println(new No309_maxProfit().maxProfit_v1(new int[]{1, 2, 3, 0, 2}));
    }

    public int maxProfit_v1(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        /*
        先定义以下数组，以及其代表的含义
        f[i][0] //持股
        f[i][1] //不持股(当天没卖出但本身也没有股票)
        f[i][2] //不持股(当天卖出了所以没有股票)

        1. 出现第i天持股情况，有以下两种可能：
        a.第i天购买的股票，第i天需要购买股票则要求第i-1天非冷却期，即第i-1天没有进行卖出行为；
        b.第i-1天就拥有的股票一直保存到第i天，第i-1天需要拥有股票，没有进行卖出行为
        f[i][0]=max(f[i-1][0],f[i-1][1]-price[i]);
              //其中f[i-1][1]代表第i-1天没有进行卖出，所以第i天当天购入股票

        2. 出现即使第i天没卖股票的但也没有股票这种情况，有以下两种可能：
        a.第i-1天就没有股票，且第i-1天也没有进行卖出
        b.第i-1天有股票，但是它在第i-1天就卖出了**
        f[i][1]=max(f[i-1][2],f[i-1][1]);
                //其中f[i-1][2]代表第i-1天卖出了股票导致第i天没有股票，
                //   f[i-1][1]代表第i-1天没有进行卖出但也没有股票的情况

        3. 第i天进行了卖出
        a.第i-1天拥有股票，第i天卖出了
        f[i][2]=f[i-1][0]+prices[i];
        */
        int[][] f = new int[n][3];
        f[0][0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - prices[i]);
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][2]);
            f[i][2] = f[i - 1][0] + prices[i];
        }
        return Math.max(f[n - 1][1], f[n - 1][2]);
    }
}
